#include "NodoArbolB.h"

void NodoArbolB::FucionarNodos(int nodo1, int nodo2, int nodo3)
{
	int aux;

	if(nodo1>nodo2)
	{
		aux=nodo1;
		nodo1=nodo2;
		nodo2=aux;
	}

	if(nodo1>nodo3)
	{
		aux=nodo1;
		nodo1=nodo3;
		nodo3=aux;
	}

	if(nodo2>nodo3)
	{
		aux=nodo2;
		nodo2=nodo3;
		nodo3=aux;
	}


	if(nodo1==-1)
	{
		if(((NodoArbolB*)nodos[nodo2])->claves.size()+((NodoArbolB*)nodos[nodo3])->claves.size()+1<(unsigned int)cantidadClaves)
		{
			MoverContenidoNodo(nodo3,nodo2,((NodoArbolB*)nodos[nodo3])->claves.size());
		}
	}
	else
	{
		//estan los 3 nodos
		if(((NodoArbolB*)nodos[nodo1])->claves.size()+((NodoArbolB*)nodos[nodo2])->claves.size()+((NodoArbolB*)nodos[nodo3])->claves.size()+2 <(unsigned int) 2*cantidadClaves)
		{
			MoverContenidoNodo(nodo2,nodo3,((NodoArbolB*)nodos[nodo3])->nodos.size());
			MoverContenidoNodo(nodo1,nodo2,((NodoArbolB*)nodos[nodo2])->nodos.size()-cantidadClaves-1);
		}
	}

}


void NodoArbolB::MoverContenidoNodo(int desde, int hasta,int cantidad)
{
	if(desde==hasta)
		return;

	if(((NodoArbolB*)nodos[desde])->nodos.size()<(unsigned int)cantidad)
		cantidad=((NodoArbolB*)nodos[desde])->nodos.size();

	if (cantidad==0)
		return;

	if(hasta<desde)
	{
		cantidad--;
		((NodoArbolB*)nodos[hasta])->claves.push_back(claves[hasta]);
		((NodoArbolB*)nodos[hasta])->nodos.push_back(((NodoArbolB*)nodos[desde])->nodos[0]);
		((NodoArbolB*)nodos[desde])->nodos.erase(((NodoArbolB*)nodos[desde])->nodos.begin());


		for(;cantidad!=0 && claves.size()!=0;cantidad--)
		{
			((NodoArbolB*)nodos[hasta])->claves.push_back(((NodoArbolB*)nodos[desde])->claves[0]);
			((NodoArbolB*)nodos[desde])->claves.erase(((NodoArbolB*)nodos[desde])->claves.begin());
			((NodoArbolB*)nodos[hasta])->nodos.push_back(((NodoArbolB*)nodos[desde])->nodos[0]);
			((NodoArbolB*)nodos[desde])->nodos.erase(((NodoArbolB*)nodos[desde])->nodos.begin());
		}


		if(((NodoArbolB*)nodos[desde])->nodos.size()>=1)
		{
			//si queda alguno
			claves[hasta]=((NodoArbolB*)nodos[desde])->claves[0];
			((NodoArbolB*)nodos[desde])->claves.erase(((NodoArbolB*)nodos[desde])->claves.begin());
		}
		else
		{
			//si quedo vacio
			vector<ComponenteArbolB*>::iterator itN;
			vector<Clave*>::iterator itC;
			for(int i=0; i!=desde; i++, ++itN, ++itC);

			claves.erase(itC);
			nodos.erase(itN);
		}

	}
	else
	{
		//desde<hasta
		cantidad--;
		((NodoArbolB*)nodos[hasta])->claves.insert(((NodoArbolB*)nodos[hasta])->claves.begin(),claves[desde]);
		((NodoArbolB*)nodos[hasta])->nodos.insert(((NodoArbolB*)nodos[hasta])->nodos.begin(),*(((NodoArbolB*)nodos[desde])->nodos.end()-1));
		((NodoArbolB*)nodos[desde])->nodos.erase(((NodoArbolB*)nodos[desde])->nodos.end()-1);


		for(;cantidad==0;cantidad--)
		{
			((NodoArbolB*)nodos[hasta])->claves.insert(((NodoArbolB*)nodos[hasta])->claves.begin(),*(((NodoArbolB*)nodos[desde])->claves.end()-1));
			((NodoArbolB*)nodos[desde])->claves.erase(((NodoArbolB*)nodos[desde])->claves.end()-1);
			((NodoArbolB*)nodos[hasta])->nodos.insert(((NodoArbolB*)nodos[hasta])->nodos.begin(),*(((NodoArbolB*)nodos[desde])->nodos.end()-1));
			((NodoArbolB*)nodos[desde])->nodos.erase(((NodoArbolB*)nodos[desde])->nodos.end()-1);
		}

		if(((NodoArbolB*)nodos[desde])->claves.size()>1)
		{
			//si queda alguno
			claves[desde]=*(((NodoArbolB*)nodos[desde])->claves.end()-1);
			((NodoArbolB*)nodos[desde])->claves.erase(((NodoArbolB*)nodos[desde])->claves.end()-1);
		}
		else
		{
			//si quedo vacio
			claves.erase(claves.begin()+desde);
			nodos.erase(nodos.begin()+desde);
		}

	}
}


void NodoArbolB::BajarMayor(Clave *dato, ComponenteArbolB *puntero)
{
	nodos.push_back(puntero);
	claves.push_back(dato);
}



void NodoArbolB::BajarMenor(Clave *dato, ComponenteArbolB *puntero)
{
	nodos.insert(nodos.begin(),puntero);
	claves.insert(claves.begin(),dato);
}



void NodoArbolB::SubirMayor(Clave * &dato, ComponenteArbolB * &puntero)
{
	if(claves.size()==0)
	{
		dato=NULL;
		puntero=NULL;
		return;
	}
	dato=claves[claves.size()-1];
	puntero=nodos[nodos.size()-1];
	claves.pop_back();
	nodos.pop_back();
}



NodoArbolB::~NodoArbolB()
{
	for(vector<ComponenteArbolB*>::iterator it=nodos.begin(); it != nodos.end(); ++it)
	{
		delete *it;
	}


	for(vector<Clave*>::iterator it=claves.begin(); it != claves.end(); ++it)
	{
		delete *it;
	}
}



bool NodoArbolB::Ingresar(Informacion *dato)
{
	bool error=false;
	int i;
	for( i=0; (unsigned int)i < claves.size();  i++)
	{
		if(dato->Comparar(claves[i])<=0)
		{
			//salgo cuando encuentro la primer clave menos
			break;
		}
	}

	//lo agrego al siguiente
	if(nodos.size()==0)
		nodos.push_back(new HojaArbolB(this->cantidadClaves));
	if((int)nodos.size()-1<i)
		i--;
	error=nodos[i]->Ingresar(dato);

	ActualizarClave(i);

	if(error)
		SolucionarDesborde( i);

	error= claves.size()==(unsigned int)cantidadClaves+1;



	return error;

}

void NodoArbolB::SolucionarDesborde(int i)
{
	int j;

	bool solucionado=false;

	if( (unsigned int)(i+1 ) < claves.size())
		j=i+1;
	else
		j=i-1;

	if(j!=-1)
	{
		MoverContenido(i,j);

		if(nodos[j]->EsHoja())
			solucionado= ((HojaArbolB*)nodos[j])->informacion.size() <= (unsigned int)cantidadClaves;
		else
			solucionado= ((NodoArbolB*)nodos[j])->nodos.size() <= (unsigned int)cantidadClaves;
	}

	if(solucionado)
		return;

	if(nodos[i]->EsHoja())
	{
		DividirHojas(i,j);
	}
	else
	{
		DividirNodos(i,j);
	}
}


bool NodoArbolB::EsHoja()
{
	return false;
}



bool NodoArbolB::Quitar(Informacion *dato)
{
	bool error=false;
	int i;
	for( i=0; (unsigned int)i < claves.size();  i++)
	{
		if(dato->Comparar(claves[i])<=0)
		{
			//salgo cuando encuentro la primer clave menor
			break;
		}
	}

	//lo quito del siguiente
	error=nodos[i]->Quitar(dato);

	ActualizarClave(i);

	if(error)
		SolucionarSubFlojo( i);

	error= claves.size()< (unsigned int)(cantidadClaves * 2/3);

	return error;
}


void NodoArbolB::SolucionarSubFlojo(int  i)
{
	int j, k;

	bool solucionado=false;

	if((unsigned int)i+1 < claves.size())
	{
		j=i+1;
		if((unsigned int)j+1 < claves.size())
			k=j+1;
		else
			k=i-1;
	}
	else
	{
		j=i-1;
		k=j-1;
	}


	if(nodos[i]->EsHoja())
	{
		if(j!=-1)
		{
			if(k!=-1)
			{

				//si tiene los dos nodos a los costados trato de compensarlo con ellos

				if(((HojaArbolB*)nodos[j])->informacion.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con los nodos de los constados
					MoverContenido(j, i);
					solucionado=true;
				}
				else if(((HojaArbolB*)nodos[k])->informacion.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con los nodos de los constados
					if(j>i && k<i)
						MoverContenido(k, i);
					else
					{
						MoverContenido(k, j);
						MoverContenido(j, i);
					}

					solucionado=true;
				}
			}
			else
			{
				//si tiene un solo nodo al costado lo trato de compensar con el

				if(((HojaArbolB*)nodos[j])->informacion.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con el nodo del costado

					MoverContenido(j, i);
					solucionado=true;
				}
			}
		}
	}
	else
	{
		if(j!=-1)
		{
			if(k!=-1)
			{

				//si tiene los dos nodos a los costados trato de compensarlo con ellos

				if(((NodoArbolB*)nodos[j])->nodos.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con los nodos de los constados
					MoverContenido(j, i);
					solucionado=true;
				}
				else if(((NodoArbolB*)nodos[k])->nodos.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con los nodos de los constados
					if(j>i && k<i)
						MoverContenido(k, i);
					else
					{
						MoverContenido(k, j);
						MoverContenido(j, i);
					}

					solucionado=true;
				}
			}
			else
			{
				//si tiene un solo nodo al costado lo trato de compensar con el

				if(((NodoArbolB*)nodos[j])->nodos.size()-1 >=(unsigned int) 2/3 *cantidadClaves)
				{
					//hay una forma de compensarlo con el nodo del costado

					MoverContenido(j, i);
					solucionado=true;
				}
			}
		}
	}

	if(solucionado)
		return;

	if(nodos[i]->EsHoja())
	{
		FucionarHojas(i,j,k);
	}
	else
	{
		FucionarNodos(i,j,k);
	}
}

void NodoArbolB::MoverContenido(int desde, int hasta)
{
	Clave* clave;
	ComponenteArbolB* nodo;

	if(nodos[desde]->EsHoja())
	{
		if(desde<hasta)
		{
			((HojaArbolB*)nodos[hasta])->informacion.insert(((HojaArbolB*)nodos[hasta])->informacion.begin(),((HojaArbolB*)nodos[desde])->informacion[((HojaArbolB*)nodos[desde])->informacion.size()-1]);
			((HojaArbolB*)nodos[desde])->informacion.pop_back();
			ActualizarClave(desde);
		}
		else
		{
			((HojaArbolB*)nodos[desde])->informacion.insert(((HojaArbolB*)nodos[desde])->informacion.begin(),((HojaArbolB*)nodos[hasta])->informacion[((HojaArbolB*)nodos[hasta])->informacion.size()-1]);
			((HojaArbolB*)nodos[hasta])->informacion.pop_back();
			ActualizarClave(hasta);
		}
	}
	else
	{
		if(desde<hasta)
		{
			((NodoArbolB*)nodos[desde])->SubirMayor(clave, nodo);
			((NodoArbolB*)nodos[hasta])->BajarMenor(clave, nodo);
			ActualizarClave(desde);
		}
		else
		{
			((NodoArbolB*)nodos[desde])->SubirMenor(clave, nodo);
			((NodoArbolB*)nodos[hasta])->BajarMayor(clave, nodo);
			ActualizarClave(hasta);
		}
	}
}

void NodoArbolB::ActualizarClave(int claveNum)
{
	if((int)claves.size()-1< claveNum)
		claves.push_back(NULL);

	if(claves[claveNum])
		delete claves[claveNum];
	nodos[claveNum]->MayorClave(claves[claveNum]);
}


void NodoArbolB::MayorClave(Clave* &dato)
{
	nodos[nodos.size()-1]->MayorClave(dato);
}

void NodoArbolB::DividirNodos(int nodo1, int nodo2)
{
	int aux, nodo3;

		if(nodo1>nodo2)
		{
			aux=nodo1;
			nodo1=nodo2;
			nodo2=aux;
		}

		nodo3=nodo2+1;

		claves.insert(claves.begin()+nodo2,NULL);
		nodos.insert(nodos.begin()+nodo2,new NodoArbolB(cantidadClaves));

		//nodo1= primero, nodo2= nuevo, nodo3= antiguo nodo2

		//le cargo manualmente el primer nodo
		((NodoArbolB*)nodos[nodo2])->nodos.push_back(((NodoArbolB*)nodos[nodo3])->nodos[0]);
		((NodoArbolB*)nodos[nodo3])->nodos.erase(((NodoArbolB*)nodos[nodo3])->nodos.begin());

		//cargo manualmente la clave
		claves[nodo2]=((NodoArbolB*)nodos[nodo3])->claves[0];
		((NodoArbolB*)nodos[nodo3])->claves.erase(((NodoArbolB*)nodos[nodo3])->claves.begin());

		//muevo 1/3 del primer nodo
		MoverContenidoNodo(nodo1,nodo2,cantidadClaves*1/3);

		//muevo el otro 1/3 desde el segundo recordando que ya pase uno manualmente
		MoverContenidoNodo(nodo3,nodo2,(cantidadClaves*1/3)-1);
}



NodoArbolB::NodoArbolB(int cantidadClaves): ComponenteArbolB(cantidadClaves)
{
	for(vector<ComponenteArbolB*>::iterator it=nodos.begin(); it != nodos.end(); ++it)
	{
		*it=NULL;
	}


	for(vector<Clave*>::iterator it=claves.begin(); it != claves.end(); ++it)
	{
		*it=NULL;
	}
}



void NodoArbolB::SubirMenor(Clave *& dato, ComponenteArbolB *& puntero)
{
	if(claves.size()==0)
	{
		dato=NULL;
		puntero=NULL;
		return;
	}
	dato=claves[0];
	puntero=nodos[0];

	nodos.erase(nodos.begin());
	claves.erase(claves.begin());
}


vector<Informacion*> NodoArbolB::Buscar(Clave* dato)
{

	int i;
	for( i=0; (unsigned int)i < claves.size();  i++)
	{
		if(dato->Comparar(claves[i])<=0)
		{
			//salgo cuando encuentro la primer clave menos
			break;
		}
	}

	return this->nodos[i]->Buscar(dato);

}

void NodoArbolB::DividirHojas(int hoja1,int hoja2)
{
	//TODO:
}

void NodoArbolB::FucionarHojas(int hoja1,int hoja2, int hoja3)
{
	//TODO:
}


